public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();

        int[] group = new int[]{2,3,5};
        int[] profit = new int[]{6,7,8};
        System.out.println(test.profitableSchemes(10, 5, group, profit));
    }

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        /**
         * 盈利计划
         *  状态表示：
         *      dp[i][j][k]表示在选取前i个工作时， 计划所需人数小于等于j 且 计划总利润大于等于k，此时最大的计划数量
         *  状态转移方程：
         *      dp[i][j][k] = dp[i-1][j][k];
         *      if(group[i-1] <= j) {
         *          if(profit[i-1] >= k) {
         *              dp[i][j][k] += dp[i-1][j-group[i-1]][0] + 1;
         *          } else {
         *              dp[i][j][k] += dp[i-1][j-group[i-1]][k-profit[i-1]]
         *          }
         *      }
         *  初始化：
         *      无需初始化
         *  填表顺序：
         *      从上到下，从左到右
         *  返回值：
         *      return dp[len][n][minProfit]
         * */
        // 1 预处理
        int len = group.length;
        int MOD = (int)Math.pow(10, 9) + 7;
        // 2 创建dp表
        int[][][] dp = new int[len+1][n+1][minProfit+1];
        // 3 初始化
        for(int h = 0; h <= n; h++) {
            dp[0][h][0] = 1;
        }
        // 4 填表
        for(int i = 1; i <= len; i++) {
            for(int j = 0; j <= n; j++) {
                for(int k = 0; k <= minProfit; k++) {
                    // -不选
                    dp[i][j][k] = dp[i-1][j][k];
                    // -选
                    if(j >= group[i-1]) {
                        if(profit[i-1] >= k) {
                            // -当前工作利润就大于等于规定利润时
                            dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-group[i-1]][0]) % MOD;
                        } else {
                            // -当前工作利润小于规定利润时
                            dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-group[i-1]][k-profit[i-1]]) % MOD;
                        }
                    }
                    dp[i][j][k] = dp[i][j][k] % MOD;
                }
            }
        }
        // 5 返回值
        return dp[len][n][minProfit];
    }
}
